perm filename 1[CRE,BGB] blob
sn#021793 filedate 1973-01-25 generic text, type T, neo UTF8
00100 I. A. DATA STRUCTURE.
00200
00300
00400 Contour-Region-Edge or CRE, is a combination of ideas; the
00500 two principle ideas being that of an elevation contour map and that
00600 of a political map. On a contour map of an island fully surrounded by
00700 ocean, no two contour lines every cross and all the contour lines
00800 close. Consequently, the loops of elevation contours enclose
00900 regions; and these regions overlap in a nested fashion forming a tree
01000 data structure. On political maps, ignoring for the moment geographic
01100 pathologies such as Vietnam and the Vatican; no two states ever
01200 overlap, the states are bounded by borders, and the regions within
01300 the borders are simply connected.
01400
01500 One idea that is emphatically not in CRE is that of a
01600 schematic line drawing. Although the CRE output can be viewed as a
01700 collection of lines on a display screen, people expecting a line
01800 drawing rendition of the given television picture will be
01900 disappointed. A CRE picture is a simple translation of the
02000 photometry, geometry and topology of the orginal video image. Whereas
02100 the typical line drawing from a human illustrator is a representation
02200 of the scene without photometric information.
02300
02400 The data structure to be discussed is implemented as small
02500 blocks of words containing pointers and data in the fashion usual to
02600 graphics and simulation; an introduction to this technology can be
02700 found in Knuth [1]. The language of implementation is PDP-10 machine
02800 code via the FAIL assembler. The direct explanation of CRE structure
02900 will be presented in three parts: first, the several kinds of nodes
03000 will be briefly explained; second, the sub-structures such as rings,
03100 trees and lists will be discribed; and third, the detailed node
03200 formats will be given.
00100 TYPES OF NODES.
00200
00300 The are several types of CRE nodes: Vector, Arc, Vertex,
00400 Polygon, Face, Edge, Image, Level, Film, Empty and Extra. At the
00500 very top of all the structure is the film node, the film node is
00600 unique and serves as an OBLIST from which all other nodes may be
00700 reached. The film node embodies the idea of a piece of celluloid
00800 film or a length of magnetic video tape; in the abstract, a sequence
00900 of images taken by the same camera of the same scene with only a
01000 small amount of action or difference between images.
01100
01200 An image node represents the familair two dimensional idea of
01300 a photograph or an oil painting. An image node has two immediate sub
01400 structures that may exist simultaneously; there is the intensity
01500 contour image composed of level and polygon nodes, and there is the
01600 winged edge image composed of faces and edges.
01700
01800 The level node represents a photometrically binary image that
01900 results from thresholding a gray scale image. Polygon nodes express
02000 the notion of never intersecting contour lines each of which always
02100 closes upon itself. Contour lines are approximated by a ring of
02200 vectors hence the term "polygon".
02300
02400 CRUDE DIAGRAM OF NODE "IMMEDIACY" BY TYPE.
02500
02600 FILM →→→ Empties
02700 ↓
02800 ↓
02900 ↓
03000 ←←←←← IMAGES →→→→→→
03100 ↓ ↓
03200 ↓ ↓
03300 ↓ ↓
03400 FACES & EDGES LEVELS & POLYGONS →→→ extras.
03500 ↓ ↓
03600 ↓ ↓
03700 ↓ ↓
03800 VECTORS, VERTICES & ARCS →→→ extras.
03900
04000 The face, edge and vertex nodes are the three elements
04100 necessary for representing the idea of a mosaic or 2D tesselation,
04200 that is a picture made of little pieces placed tightly side by side
04300 to completely cover the image wihtout overlapping.
04400
04500 Empty nodes and Extra nodes are artifacts of the fixed block
04600 size dynamic storage allocation mechanism used in CRE. Entities are
04700 made by taking blocks from an AVAIL list of empty nodes and entities
04800 are killed by returning the block to the AVAIL list; there is no
04900 garbage collector, but there is a space compactor called SHRINK.
05000 Extra nodes are used to provide additional space for the ARC and
05100 POLYGON nodes; so that ARC and POLYGON are double sized nodes.
00100 CRE SUB-STRUCTURES:
00200
00300 SEVEN RINGS.
00400 1. Image Ring of a Film.
00500 2. Level Ring of an Image.
00600 3. Polygon Ring of a Level.
00700 4. Vector Ring of a Polygon.
00800 5. Arc Ring of a Polygon.
00900 6. Face Ring of an Image.
01000 7. Edge Ring of an Image.
01100
01200 THREE PAIRS.
01300 1. Arc↔Vector Pairs.
01400 2. Vector↔Vector Radial Pairs.
01500 3. Arc↔Arc Radial Pairs.
01600
01700 TWO TREES.
01800 1. The Tree of Rings.
01900 2. The Polygon Tree.
02000
02100 TWO LISTS.
02200 1. Time Lists.
02300 2. The empty node list.
02400
02500 ONE EULER GRAPH.
02600 1. Winged Edge Structure - Face, Edge, Vertex.
00100 VECTOR/ARC/VERTEX NODE FORMAT.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | vector ring |
00600 _____|___________________|___________________|
00700 word | ROW | COL |
00800 1 | ∂ 0000.00 | ∂ 0000.00 |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | ∂ 1 | ∂ 303 313 |
01200 _____|___________________|___________________|
01300 word | | |
01400 3 | ENDO | EXO |
01500 _____|___________________|___________________|
01600 word | | |
01700 4 | ARC | PED |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | ∂ CNTRST | PGON |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 POLYGON NODE FORMAT.
02800
02900 _____________________________________________
03000 word | CW | CCW |
03100 0 | polygon ring |
03200 _____|___________________|___________________|
03300 word | DAD | SON |
03400 1 | level | 1st vector |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | 10 | 333 233 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | ENDO | EXO |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | ARC | NCNT |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | NGON | PGON |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | NTIME | PTIME |
05000 _____|___________________|___________________|
00100 THE VECTOR/ARC/VERTEX NODE.
00200
00300 The most numerous kind of node is the VECTOR/ARC/VERTEX,
00400 which for informal discussion will be called a VERTEX.
00500
00600 Vertices carry the fundamental geometric datum of an image locus. The
00700 image locus is stored in halfword positions named ROW and COL, which
00800 contain the row and column of a point in units 1/64 of a pixel. A
00900 "pixel" is a "picture element".
01000
01100 Vertices when used as vectors or arcs also carry the fundamental
01200 photometric datum of edge contrast. Fundamental data is that data
01300 which comes almost irectly from the video image and is used to
01400 compute other data such face area or region gradient.
01500
01600 Vertices always belong to a polygon node, a pointer to the polygon of
01700 each vertex is stored in the link named PGON; as members of a polygon
01800 the vertices form a perimeter or loop which is always connected so
01900 that each vertex has a neighboring vertex in the clockwise and in the
02000 counter clockwise directions about the polygon's perimeter. There
02100 perimeter pointers re stored in the link positions named CW and CCW.
02200
02300 The links named NTIME and PTIME appear in all nodes except
02400 the film node; these links connect corresponding parts of a given
02500 image with parts of its immediate predecessor image and with parts of
02600 its immediate successor image. Time links implement the notion of a
02700 film where each frame differs but little from its neighboring frames
02800 along the film.
00100 THE EDGE NODE FORMAT.
00200
00300 _____________________________________________
00400 word | NCW clockwise NCW |
00500 0 | wings |
00600 _____|___________________|___________________|
00700 word | NCCW counter PCCW |
00800 1 | clockwise wings |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | ∂ 02 | ∂ 400 000 |
01200 _____|___________________|___________________|
01300 word | | |
01400 3 | NFACE | PFACE |
01500 _____|___________________|___________________|
01600 word | edge-ring |
01700 4 | NED | PED |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | NVT | PVT |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 WINGED EDGE MANDALA:
02800
02900 \ /
03000 nccw \ / pcw
03100 \ /
03200 ⊗ pvt
03300 |
03400 nface E pface
03500 |
03600 nvt ⊗
03700 / \
03800 ncw / \ pccw
03900 / \
00100 FACE NODE FORMAT.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | vector ring |
00600 _____|___________________|___________________|
00700 word | DAD | |
00800 1 | image | |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | ∂ 04 | ∂ 023 103 |
01200 _____|___________________|___________________|
01300 word | face-ring |
01400 3 | NFACE | PFACE |
01500 _____|___________________|___________________|
01600 word | | |
01700 4 | | PED |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | ∂ PERIM | ∂ AREA |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 FILM NODE FORMAT.
02800
02900 _____________________________________________
03000 word | | |
03100 0 | | core size |
03200 _____|___________________|___________________|
03300 word | | SON |
03400 1 | | image |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | ∂ 100 | 011 000 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | | |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | | |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | | |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | | |
05000 _____|___________________|___________________|
00100 IMAGE NODE FORMAT.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | image ring |
00600 _____|___________________|___________________|
00700 word | DAD | SON |
00800 1 | film | level |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | 40 | 333 333 |
01200 _____|___________________|___________________|
01300 word | face ring |
01400 3 | NFACE | PFACE |
01500 _____|___________________|___________________|
01600 word | edge ring |
01700 4 | NED | PED |
01800 _____|___________________|___________________|
01900 word | vertex ring |
02000 5 | NVT | PVT |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 LEVEL NODE FORMAT.
02800
02900 _____________________________________________
03000 word | CW | CCW |
03100 0 | level ring |
03200 _____|___________________|___________________|
03300 word | DAD | SON |
03400 1 | image | polygon |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | ∂ 20 | ∂ 330 003 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | | |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | | |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | | |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | NTIME | PTIME |
05000 _____|___________________|___________________|